package com.lw.leetcode.tree.c;

import com.lw.test.util.Utils;

/**
 * Created with IntelliJ IDEA.
 * 493. 翻转对
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/2 17:13
 */
public class ReversePairs {

    public static void main(String[] args) {
        ReversePairs test = new ReversePairs();

        // 2
//        int[] arr = {1,3,2,3,1};

        // 3
//        int[] arr = {2,4,3,5,1};

        // 3
//        int[] arr = {-5, -5};

        // 313304605
        int[] arr = Utils.getArr(50, Integer.MIN_VALUE, Integer.MAX_VALUE);

        int i = test.reversePairs(arr);
        System.out.println(i);
    }

    public int reversePairs(int[] nums) {
        Node root = new Node(Integer.MIN_VALUE, Integer.MAX_VALUE);
        int sum = 0;
        int l = (Integer.MAX_VALUE >> 1);
        for (int num : nums) {
            if (num <= l) {
                sum += find(root, (((long)num) << 1));
            }
            add(root, num);
        }
        return sum;
    }

    private int find(Node node, long value) {
        if (node == null) {
            return 0;
        }
        long st = node.st;
        long end = node.end;
        long m = st + ((end - st) >> 1);
        if (m < value) {
            return find(node.right, value);
        } else {
            return find(node.left, value) + (node.right == null ? 0 : node.right.count);
        }
    }

    private void add(Node node, int value) {
        long st = node.st;
        long end = node.end;
        node.count++;
        if (st == end) {
            return;
        }
        long m = st + ((end - st) >> 1);
        if (value <= m) {
            if (node.left == null) {
                node.left = new Node(st, m);
            }
            add(node.left, value);
        } else {
            if (node.right == null) {
                node.right = new Node(m + 1, end);
            }
            add(node.right, value);
        }
    }

    private static class Node {
        private long st;
        private long end;
        private int count;
        private Node left;
        private Node right;

        private Node(long st, long end) {
            this.st = st;
            this.end = end;
        }
    }
}
